class Solution {
private:
    void dfs(vector<vector<char>>& grid, int a, int b)
    {
        int na = grid.size();
        int nb = grid[0].size();
        
        grid[a][b] = '0';
        if(a-1>=0 && grid[a-1][b]=='1') dfs(grid,a-1,b);
        if(a+1<na && grid[a+1][b]=='1') dfs(grid,a+1,b);
        if(b-1>=0 && grid[a][b-1]=='1') dfs(grid,a,b-1);
        if(b+1<nb && grid[a][b+1]=='1') dfs(grid,a,b+1);
    }

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int na = grid.size();
        if (!na) return 0;
        int nb = grid[0].size();

        int num_islands = 0;
        for (int a = 0; a < na; ++a) 
        {
            for (int b = 0; b < nb; ++b) 
            {
                if (grid[a][b] == '1') 
                {
                    ++num_islands;
                    dfs(grid, a, b);
                }
            }
        }
        return num_islands;
    }
};